class Solution {
public:
    string s1;
    string s2;
    int dp[30][30][31];//长度最大为30，下标从0开始，长度从1开始
    //方便说，s2是s1的扰乱字符串，称为和谐
    //0表示未比较，-1表示不和谐，1表示和谐
    bool CheckCharIsEqual(int i,int j,int length)
    {
        unordered_map<int,int> map;

        for(int k = i; k < i + length; ++k)
        {
            map[s1[k] - 'a']++;
        }

        for(int k = j; k < j + length; ++k)
        {
            map[s2[k] - 'a']--;
        }

        if(any_of(map.begin(),map.end(),[](const auto& e){return e.second != 0;}))//成立表示存在字符不相等
        {
            return false;
        }

        return true;
    }
    bool dfs(int i,int j,int length)
    {
        if(dp[i][j][length])//已经比较过了
            return dp[i][j][length] == 1;

        if(s1.substr(i,length) == s2.substr(j,length))//字符串相等
        {
            dp[i][j][length] = 1;
            return true;
        }

        if(s1.substr(i,length).size() != s2.substr(j,length).size())
        {
            dp[i][j][length] = -1;
            return false;
        }

        if(!CheckCharIsEqual(i,j,length))//不相同，一定不和谐
        {
            dp[i][j][length] = -1;
            return false;
        }

        for(int pos = 1; pos < length; ++pos)//遍历分割位置
        {
            if(dfs(i,j,pos) && dfs(i + pos,j + pos,length - pos))//不交换
            {
                dp[i][j][length] = 1;
                return true;
            }

            if(dfs(i,j + length - pos,pos) && dfs(i + pos,j,length - pos))//交换
            {
                dp[i][j][length] = 1;
                return true;
            }
        }

        dp[i][j][length] = -1;

        return false;
    }
    bool isScramble(string str1, string str2) 
    {
        //状态表示：dp[i][j]表示s2[0...j]是否是s1[0...i]的扰乱字符串
        //状态转移方程：如果s1[0...i]与s2[0...j]的长度不相同，dp[i][j] = false
        //如果s1[0...i]和s2[0...j]相等的话，dp[i][j] = true;
        //如果其中某个字符在s1[0...i]和s2[0...j]出现次数不一致的话，dp[i][j] = false;
        //遍历切割长度pos，length = j - 0 + 1，如果有交换的话。查看dp[0...pos][j + length - pos...j + length - pos] && dp[pos,length - 1][j,pos]，如great和eatgr，pos = 1，有交换的情况下，分别为gr eat和eat gr，为dp[0...1][...4]
        //注意，上面的遍历切分长度是错误的，很混乱

        //状态表示修改为：dp[i][j][length]，表示在s1从i开始，s2从j开始，长度为length，s2是否是s1的扰乱字符串
        //因为用到了length，直接最开始传入字符串的长度，dfs下去，知道s1和s2都剩下一个字符，再一层一层回来，由于可能结果重复计算，直接改为记忆性搜索

        memset(dp,0,sizeof(dp));

        s1 = str1;
        s2 = str2;
        
        return dfs(0,0,str1.size());
    }
};

/*
使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
如果字符串的长度为 1 ，算法停止
如果字符串的长度 > 1 ，执行下述步骤：
在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。如果是，返回 true ；否则，返回 false 。

示例 1：
输入：s1 = "great", s2 = "rgeat"
输出：true
解释：s1 上可能发生的一种情形是：
"great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
"gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
"gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
"g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
"r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
"r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
算法终止，结果字符串和 s2 相同，都是 "rgeat"
这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true
*/